package offer;

import common.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author fance
 * @date 18-4-1 下午12:19
 */
public class Chapter2 {
    // 1.单例 所有实现 5.替换空格:replaceAll O(1) 方法 :记录空格数 需要增加空格数*2 长度,从尾到头赋值 15.n & (n - 1)


    public boolean search(int[][] arr, int target) {
        int i = 0;
        int j = arr[0].length - 1;
        while (i < arr.length && j >= 0) {
            if (arr[i][j] > target) {
                j--;
            } else if (arr[i][j] < target) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }


    public double myPower(double base, int exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp == 1) {
            return base;
        }
        boolean neg = false;
        if (exp < 0) {
            neg = true;
            exp = -exp;
        }
        double ret = 1.0;
        ret = myPower(base, exp >> 1);
        ret *= ret;
        if ((exp & 1) != 0) {
            ret *= base;
        }
        if (neg) {
            ret = 1.0 / ret;
        }
        return ret;

    }

    public List<List<Integer>> findPath(TreeNode root, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        dfs(root, target, 0, new ArrayList<Integer>(), ret);
        return ret;
    }
    private void dfs(TreeNode node, int target, int curSum, List<Integer> path, List<List<Integer>> res) {
        if (node == null) {
            return;
        }
        curSum += node.val;
        path.add(node.val);
        if (curSum == target && node.left == null && node.right == null) {
            res.add(new ArrayList<Integer>(path));
        } else {
            dfs(node.left, target, curSum, path, res);
            dfs(node.right, target, curSum, path, res);
        }
        path.remove(path.size() - 1);
    }

    public List<Integer> maxInWindows(int[] num, int size) {
        List<Integer> ret = new ArrayList<>();
        int len = num.length;
        if (num == null || size <= 0 || size > len) {
            return ret;
        }
        ArrayList<Integer> tmp = null;
        for (int i = 0; i < len - size + 1; i++) {
            tmp = new ArrayList<>();
            for (int j = i; j < size + i; j++) {
                tmp.add(num[j]);
            }
            Collections.sort(tmp);
            ret.add(tmp.get(tmp.size() - 1));
        }
        return ret;
    }


    public int strToInt(String str) {
        if (str.length() == 0) {
            return 0;
        }
        char[] chars = str.toCharArray();
        boolean isNeg = chars[0] == '-';
        int ret = 0;
        for (int i = 0; i < chars.length; i++) {
            if (i == 0 && (chars[i] == '+' || chars[i] == '-')) {
                continue;
            }
            if (chars[i] < '0' || chars[i] > '9') {
                return 0;
            }
            ret = ret * 10 + (chars[i] - '0');
        }
        return isNeg ? -ret : ret;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }


    @Test
    public void test() {
        /*int[] a = {2,3,4,2,6,2,5,1};
        List<Integer> res = maxInWindows(a, 3);
        for (int n: res
             ) {
            System.out.println(n);
        }*/

        //System.out.println(myPower(2, -3));
        System.out.println();
    }
}
